package algorithms

import (
// "io/ioutil" //io 工具包
)

//快速排序
func QuickSort(low int, high int, arr []int) {
	if low >= high {
		return
	}
	m := func(a int, b int) int {
		temp := arr[low]
		for a < b {
			//从后往前
			for a < b && arr[b] > temp {
				b--
			}
			if a < b {
				arr[a] = arr[b]
				a++
			}

			//从前往后
			for a < b && arr[a] < temp {
				a++
			}
			if a < b {
				arr[b] = arr[a]
				b--
			}
		}
		arr[a] = temp
		return a
	}(low, high)
	QuickSort(low, m-1, arr)
	QuickSort(m+1, high, arr)
}

//多线程将排序后的值写入chan
func Quicksort(nums []int, ch chan int, level int, threads int) {
	level = level * 2
	if len(nums) == 1 {
		ch <- nums[0]
		close(ch)
		return
	} //ch<-nums[0] 表示将nums[0] 数据写到ch通道中
	if len(nums) == 0 {
		close(ch)
		return
	}

	less := make([]int, 0) //
	greater := make([]int, 0)
	left := nums[0] //快速排序的轴
	nums = nums[1:]

	//从左向右扫描数据 大于轴的放到greater里小于的放到less中
	for _, num_data := range nums {
		switch {
		case num_data <= left:
			less = append(less, num_data)
		case num_data > left:
			greater = append(greater, num_data)
		}
	}

	left_ch := make(chan int, len(less))
	right_ch := make(chan int, len(greater))

	if level <= threads {
		go Quicksort(less, left_ch, level, threads) //分任务
		go Quicksort(greater, right_ch, level, threads)
	} else {
		Quicksort(less, left_ch, level, threads)
		Quicksort(greater, right_ch, level, threads)
	}

	//合并数据
	for i := range left_ch {
		ch <- i
	}
	ch <- left
	for i := range right_ch {
		ch <- i
	}
	close(ch)
	return
}
